class Solution
{
public:
    Solution() {}
    bool canJump(vector<int> &nums)
    {
        int target = nums.size() - 1;
        int stepRemain = 0;
        // 尝试结合一步一步走与官方题解，使得第一次发现能到或不能到就停止
        // 似乎并不能提升性能
        for (int i = 0; i < target; ++i)
        {
            --stepRemain;
            if (nums[i] > stepRemain)
            {
                stepRemain = nums[i];
            }
            if (stepRemain == 0)
            {
                return false;
            }
            if (i + stepRemain >= target)
            {
                return true;
            }
        }
        // 应该运行不到这里
        return true;
    }

private:
    // 暴力递归，超时
    bool canJump(vector<int> &nums, int index)
    {
        if (index == 0)
        {
            return true;
        }
        else
        {
            for (int i = 0; i < index; ++i)
            {
                if ((nums[i] >= (index - i) && canJump(nums, i)))
                {
                    return true;
                }
            }
            return false;
        }
    }

    bool canJumpStepBy(vector<int> &nums)
    {
        int target = nums.size() - 1;
        int stepRemain = 0;
        // 一步一步走，但每次都更新剩余的最大步数，保证利用nums的每一个值
        // 与官方题解相比，本方法在不能到达时，不必遍历完整个列表，但在可以到达时一定会遍历整个列表
        // 官方题解则正好相反，在可以到达时，未必需要遍历整个列表
        for (int i = 0; i < target; ++i)
        {
            --stepRemain;
            if (nums[i] > stepRemain)
            {
                stepRemain = nums[i];
            }
            if (stepRemain == 0)
            {
                return false;
            }
        }
        return true;
    }
};